package com.sicheng.algorithm.math;

public class NumberOfOne {

    /**
     * 题目描述
     * 输入一个整数，输出该数二进制表示中 1 的个数。
     */
    public static void main(String[] args) {
        System.out.println(numberOf1(4));
    }

    /**
     * 解题思路
     * <p>
     * n&(n-1) 位运算可以将 n 的位级表示中最低的那一位 1 设置为 0。
     * 不断将 1 设置为 0，直到 n 为 0。时间复杂度：O(M)，
     * 其中 M 表示 1 的个数
     */
    public static int numberOf1(int n) {
        int cnt = 0;
        while (n != 0) {
            cnt++;
            n &= (n - 1);
        }
        return cnt;
    }
}
